package DynamicProgrammingPackage;

/**
 * @author Lzm
 * @version 1.0
 */
public class packageNote {
  // 背包问题
  // 1. dp[i][j]表示[0,i]物品放到容量为j的背包的价值为dp[i][j]
  // 2. 递推公式: 不放i, dp[i - 1][j] 放i dp[i - 1][j - weight[i]] + value[i]
  // 则dp[i][j] = Math.max(dp[i - 1][j] ,dp[i - 1][j - weight[i]] + value[i])
  // 3. 初始化dp[0][j] = value[0] dp[i][0] = 0 要求dp[i][j]的上方和左上方必须有值
  // 4. 遍历 先遍历物品后遍历背包 和 先遍历背包后遍历物品都可 因为不管先遍历什么 dp[i][j]上方和左上方都有值

  // 一维数组
  // 1. dp[j]表示容量为j的背包的最大价值为dp[j]
  // 2. 递推公式: dp[j] = Math.max(dp[j],dp[j - weight[i] + value[i]])
  // 3. 初始化dp[0] = 0;
  // 4. 遍历顺序 先遍历物品后遍历背包, 且倒序遍历背包
}
